package com.lims.algorithm.algset.graph.iterator;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-08-24 15:23
 */
public class GraphUDG {
    /**
     * 顶点集合
     */
    private ArrayList<String> vertexList;
    /**
     * 边 矩阵
     */
    private int[][] edges;
    /**
     * 边的数目
     */
    private int num;
    /**
     * 记录被访问了的节点
     */
    public boolean[] isVisited;

    public ArrayList<String> getVertexList() {
        return vertexList;
    }

    public void setVertexList(ArrayList<String> vertexList) {
        this.vertexList = vertexList;
    }

    public int[][] getEdges() {
        return edges;
    }

    public void setEdges(int[][] edges) {
        this.edges = edges;
    }

    public int getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    /**
     * 构造函数
     */
    public GraphUDG(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        num = 0;
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     *
     * @param vertex
     */
    public void addVer(String vertex) {
        vertexList.add(vertex);
    }

    /**
     * 添加边
     *
     * @param v1     下标
     * @param v2     下标
     * @param weight 权重
     */
    public void addNum(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        num++;
    }

    /**
     * 返回节点个数
     *
     * @return
     */
    public int nodeNum() {
        return vertexList.size();
    }

    /**
     * 返回边一共多少条
     *
     * @return
     */
    public int edgeNum() {
        return num;
    }

    /**
     * 返回索引返回值
     *
     * @param i
     * @return
     */
    public String getValue(int i) {
        return vertexList.get(i);
    }

    /**
     * 返回v1，v2权重
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }

    /**
     * 显示图的矩阵
     */
    public void show() {
        System.out.println("图邻接矩阵显示：");
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
        System.out.printf("\n");
    }

    /**
     * 得到第一个邻接节点的下标
     *
     * @param index
     * @return
     */
    public int getFirstAjcVer(int index) {
        for (int j = 0; j < vertexList.size(); j++) {
            // 存在边
            if (edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据本节点前一个邻接节点的下标找本节点的下一个邻接节点
     *
     * @param v1 本节点下标
     * @param v2 前一个邻接节点下标
     * @return
     */
    public int getNextAjcVer(int v1, int v2) {
        for (int j = v2 + 1; j < vertexList.size(); j++) {
            if (edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * v1下一个未被访问过的邻接点
     *
     * @param v1
     * @return
     */
    public int getNextNoAccessAjcVer(int v1) {
        for (int j = 0; j < vertexList.size(); j++) {
            // 存在边
            if (edges[v1][j] > 0 && !isVisited[j]) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 清空访问记录
     */
    public void clearVisited() {
        isVisited = new boolean[vertexList.size()];
    }

    /**
     * 深度优先遍历
     */
    public void DFS() {
        System.out.println("深度优先遍历");
        // 遍历所有节点进行DFS
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    /**
     * 深度优先遍历
     *
     * @param isVisited
     * @param i         随机一个节点下标i
     */
    private void DFS(boolean[] isVisited, int i) {
        // 访问节点i
        System.out.print(getValue(i));
        // 节点设置为已访问
        isVisited[i] = true;
        // 查找第一个邻接节点
        int w = getFirstAjcVer(i);
        while (w != -1) {
            // 邻接节点是否已访问
            if (!isVisited[w]) {
                System.out.print("->");
                // 递归深度遍历
                DFS(isVisited, w);
            }
            // 节点已访问，查找下一个邻接节点
            w = getNextAjcVer(i, w);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        System.out.println("广度优先遍历");
        // 遍历所有节点进行DFS
        for (int i = 0; i < nodeNum(); i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void BFS(boolean[] isVisited, int i) {
        // 队列头
        int h;
        // 邻接节点
        int w;
        Deque<Integer> deque = new LinkedBlockingDeque<>();
        System.out.print(getValue(i));
        isVisited[i] = true;
        deque.addLast(i);
        while (!deque.isEmpty()) {
            // 取出队列头节点下标
            h = deque.removeFirst();
            w = getFirstAjcVer(h);
            while (w != -1) {
                if (!isVisited[w]) {
                    System.out.print("->");
                    System.out.print(getValue(w));
                    isVisited[w] = true;
                    // 入队列
                    deque.addLast(w);
                }
                // 本节点的邻接遍历完之后，本节点邻接节点的下一个邻接节点
                w = getNextAjcVer(h, w);
            }
        }
    }

    /**
     * 深度优先遍历（非递归）
     */
    public void DFSNoRecur() {
        System.out.println("深度优先遍历--非递归:");
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                DFSNoRecur(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void DFSNoRecur(boolean[] isVisited, int i) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 第一次访问 并入栈
        System.out.print(getValue(i));
        isVisited[i] = true;
        stack.push(i);
        // 循环——直到栈为空
        while (!stack.isEmpty()) {
            // 取栈顶
            int peek = stack.peek();
            // 栈顶下一个未访问过的邻接点
            int ajc = getNextNoAccessAjcVer(peek);
            // 如果邻接点存在，则访问，入栈
            if (ajc != -1) {
                System.out.print("->");
                System.out.print(getValue(ajc));
                isVisited[ajc] = true;
                stack.push(ajc);
            } else {
                // 邻接点不存在，弹出栈顶（相当于递归调用到底后返回）
                stack.pop();
            }
        }
    }

    /**
     * 深度优先遍历（非递归方法2）
     */
    public void DFSNoRecur2() {
        System.out.println("深度优先遍历--非递归方法2:");
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]) {
                DFSNoRecur2(isVisited, i);
            }
        }
        System.out.printf("\n");
    }

    private void DFSNoRecur2(boolean[] isVisited, int i) {
        Deque<Integer> stack = new ArrayDeque<>();
        // 第一次访问
        System.out.print(getValue(i) + "->");
        isVisited[i] = true;
        stack.push(i);
        while (!stack.isEmpty()) {
            // 1.找出邻接顶点
            int ajcVer;
            if (stack.size() == 1) {
                // 栈中只有一个元素时，取其第一个邻接顶点
                ajcVer = getFirstAjcVer(stack.peek());
            } else {
                // 先取出栈顶（即刚访问过的顶点）
                Integer v1 = stack.pop();
                // 栈中还有元素时，取其除了新栈顶的下一个邻接顶点（新栈顶元素对应顶点已访问过）
                ajcVer = getNextAjcVer(v1, stack.peek());
                // 取出邻接顶点后，取出的元素重新压入栈
                stack.push(v1);
            }

            // 2.没有邻接点时，弹出栈顶，相当于递归调用到底的返回
            if (ajcVer == -1) {
                Integer v2 = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                ajcVer = getNextAjcVer(stack.peek(), v2);
            }
            // 3.访问邻接点，并压栈
            if (ajcVer != -1) {
                if (!isVisited[ajcVer]) {
                    System.out.print(vertexList.get(ajcVer) + "->");
                    isVisited[ajcVer] = true;
                    // 访问过的压栈
                    stack.push(ajcVer);
                } else {
                    stack.pop();
                }
            }
        }
    }


    /*****************************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 10;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        GraphUDG udg = new GraphUDG(n);
        // 向图对象添加节点
        for (String s : vertexString) {
            udg.addVer(s);
        }

        // 添加边AB AC AD AE BC BD CE DE DF DG EH EI IJ
        udg.addNum(0, 1, 1);
        udg.addNum(0, 2, 1);
        udg.addNum(0, 3, 1);
        udg.addNum(0, 4, 1);
        udg.addNum(1, 2, 1);
        udg.addNum(1, 3, 1);
        udg.addNum(2, 4, 1);
        udg.addNum(3, 4, 1);
        udg.addNum(3, 5, 1);
        udg.addNum(3, 6, 1);
        udg.addNum(4, 7, 1);
        udg.addNum(4, 8, 1);
        udg.addNum(8, 9, 1);

        udg.show();

        udg.DFS();
        udg.clearVisited();
        udg.BFS();
        udg.clearVisited();
        udg.DFSNoRecur();
    }
}













